package algorithm.t202112;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/13 10:49
 * @description :3道
 * 一会去跑步，可能是在陕服的倒数一二次跑步了，今年的冬至是21号，那天晚上我要睡在西安，也不知道能不能跑成，这学期就这样结束了啊，结束了啊，唉，
 现在想起来今年7月1号，当时舍不得的大三，不想回家，因为一旦坐上回家的车，下次再左就是大四了，现在呢，大四上半学期已经结束了，其实下半学期已经不算是
 学期了，唉，这个寒假也是学生时代最后的假期，也是最后的寒假，不知道以后的寒假我都会怎么样度过。回想，三年前的寒假，也就是大一上半学期的寒假，那个寒假我
 去了浙江电子厂打工，过年才回来，而这次的寒假，大四上半学期的寒假，我也要出去上班，过年才回去，也算是’对称‘了，开始和结束。故事也还算圆满吗？
 心中真的很不舍很不舍，不舍的不止是这个学校，还有太多太多东西，还以就是心中的不安（无法掌握未来的不安），唉，谁的青春不迷茫（现在我还算是青春），即将
 就要踏上舞台，演绎我的人生。努力。
 persevere to last
 2021.12.13
 李红磊
 2021年12月13日19:22:04
 */
public class t20211213 {

    //807.保持城市天际线
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int rows = grid.length, columns = grid[0].length;
        int ans = 0;

        int[] row_max = new int[columns];//用于记录每一行的最大值，下标表示哪一行。例如：[4,6,8]，表示，第0行最大值为4，第1行最大值为6
        int[] col_max = new int[rows];//用于记录每一列的最大值

        //记录最大行列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                row_max[i] = Math.max(row_max[i], grid[i][j]);
                col_max[j] = Math.max(col_max[j], grid[i][j]);
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                ans += Math.min(row_max[i], col_max[j]) - grid[i][j];
            }
        }
        return ans;
    }

    //75.颜色分类
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) return;

        int idx = 0;

        //对0进行排序
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                int tem = nums[idx];
                nums[idx++] = 0;
                nums[i] = tem;
            }
        }

        //对1进行排序
        for (int i = idx; i < len; i++) {
            if (nums[i] == 1) {
                int tem = nums[idx];
                nums[idx] = 1;
                nums[i] = tem;
            }
        }

    }

    //56.合并区间
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> ans = new ArrayList<>();

        Arrays.sort(intervals, (x, y) -> x[0] - y[0]);

        for (int i = 0; i < intervals.length; i++) {
            int l = intervals[i][0], r = intervals[i][1];

            if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < l) {
                ans.add(new int[]{l, r});
            } else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], r);
            }

        }

        return ans.toArray(new int[ans.size()][]);
    }

    public static void main(String[] args) {

        t20211213 t20211213 = new t20211213();
        t20211213.merge(new int[][]{
                {1, 3},
                {2, 6},
                {8, 10},
                {15, 18}
        });


    }


}
